/*	talmud - The TALMUD roguelike
 * Copyright (C) 2012, talmud contributors
 *
 *  This program is free software; you can redistribute it and/or modify it
 *  under the terms of Version 2 of the GNU General Public License as published
 *  by the Free Software Foundation.
 *
 *  This program is distributed in the hope that it will be useful, but WITHOUT
 *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 *  FITNESS FOR A PARTICULAR PURPOSE. See Version 2 of the GNU General Public
 *  License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program; if not, write to the Free Software Foundation, Inc.,
 *  59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */

#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dlvl.h"
#include "talmud.h"
#include "rand.h"
#include "draw.h"
#include "monstermanage.h"
#include "itemmanage.h"

#define ROOMGRID_W	4
#define ROOMGRID_H	2

typedef struct room_s
{
	uint8_t matrixx;
	uint8_t matrixy;
	uint8_t x;
	uint8_t y;
	uint8_t w;
	uint8_t h;
} room_t;

typedef struct passage_s
{
	uint8_t sx;
	uint8_t sy;
	uint8_t sw;
	uint8_t sh;
	uint8_t dx;
	uint8_t dy;
	uint8_t dw;
	uint8_t dh;
	uint8_t orient;
} passage_t;

static uint8_t TILEATTRS[T_COUNT] = {
	A_WHITE,
	A_WHITE,
	A_BLUE,
	A_RED,
	A_WHITE,
	A_WHITE,
	A_INTENSE | A_WHITE,
	A_INTENSE | A_BLUE,
#if _16COLOR
	A_INTENSE | A_BLACK,
#else
	A_YELLOW,
#endif
};

static uint8_t TILECHARS[T_COUNT] = {
	'#',
	'.',
	'{',
	'@',
	'<',
	'>',
	'#',
	'^',
	'.',
};

void PlaceRoom(dlvl_t *dlvl, const room_t *room, uint8_t forcetile, uint8_t level, uint8_t branch)
{
	uint8_t x;
	uint8_t y;
	uint8_t roll;
	uint8_t spcl;
	uint8_t forceprob = room->w * room->h;
	uint8_t itemcount;
	uint8_t idx;

	spcl = 0;
	for (x = room->x; x <= room->x + room->w; x++)
	{
		for (y = room->y; y <= room->y + room->h; y++)
		{
			if (forcetile && !rn3(forceprob))
			{
				dlvl->tiles[y * DLVL_W + x] = forcetile;
				if (forcetile == T_UPSTAIR)
				{
					dlvl->upstair.x = x;
					dlvl->upstair.y = y;
				}
				else if (forcetile == T_DNSTAIR)
				{
					dlvl->dnstair.x = x;
					dlvl->dnstair.y = y;
				}
				forcetile = 0;
				continue;
			}
			roll = rn1(100);
			if (!roll && !spcl)
			{
				spcl++;
				if (!rn3i(2))
				{
					dlvl->tiles[y * DLVL_W + x] = T_POOL;
				}
				else if (!rn3i(4))
				{
					dlvl->tiles[y * DLVL_W + x] = T_IDOL;
				}
				else
				{
					dlvl->tiles[y * DLVL_W + x] = T_DTRAP;
				}
			}
			else
			{
				dlvl->tiles[y * DLVL_W + x] = T_FLOOR;
			}
			forceprob--;
		}
	}

	itemcount = rn2(3);
	for (idx = 0; idx < itemcount; idx++)
	{
		GenItemAt(room->x + rn1(room->w + 1), room->y + rn1(room->h + 1), level, branch);
	}
}

#define DIR_XYX		0
#define DIR_YXY		1
void PlaceCorridor(dlvl_t *dlvl, const passage_t *pass)
{
	uint8_t sx;
	uint8_t sy;
	uint8_t tx;
	uint8_t ty;
	uint8_t x;
	uint8_t y;
	uint8_t roll;
	uint8_t breakpoint;
	uint8_t dir;

	switch (pass->orient)
	{
		case 2:
			sx = pass->sx + rn1(pass->sw + 1);
			sy = pass->sy + pass->sh + 1;
			tx = pass->dx + rn1(pass->dw + 1);
			ty = pass->dy;
			dir = DIR_YXY;
			break;
		case 3:
			roll = rn1(2);
			if (!roll)
			{
				sx = pass->sx + pass->sw + 1;
				sy = pass->sy + (pass->sh >> 1) + rn1((pass->sh >> 1) + 1);
				tx = pass->dx;
				ty = pass->dy + rn1((pass->dh >> 1) + 1);
				dir = DIR_XYX;
			}
			else
			{
				sx = pass->sx + (pass->sw >> 1) + rn1((pass->sw >> 1) + 1);
				sy = pass->sy + pass->sh + 1;
				tx = pass->dx + rn1((pass->dw >> 1) + 1);
				ty = pass->dy;
				dir = DIR_YXY;
			}
			break;
		case 4:
			sx = pass->sx + pass->sw + 1;
			sy = pass->sy + rn1(pass->sh + 1);
			tx = pass->dx;
			ty = pass->dy + rn1(pass->dh + 1);
			dir = DIR_XYX;
			break;
		case 9:
			roll = rn1(2);
			if (!roll)
			{
				sx = pass->sx + pass->sw + 1;
				sy = pass->sy + rn1((pass->sh >> 1) + 1);
				tx = pass->dx;
				ty = pass->dx + (pass->dh >> 1) + rn1((pass->dh >> 1) + 1);
				dir = DIR_XYX;
			}
			else
			{
				sx = pass->sx + (pass->sw >> 1) + rn1((pass->sw >> 1) + 1);
				sy = pass->sy;
				tx = pass->dx + rn1((pass->dh >> 1) + 1);
				ty = pass->dy + pass->dh;
				dir = DIR_YXY;
			}
			break;
		default:
			Bug("PlaceCorridor");
			return;
	}

	x = sx;
	y = sy;
	if (dir == DIR_XYX)
	{
		breakpoint = sx + 2 + rn1(tx - sx - 4);
		while (x != breakpoint)
		{
			dlvl->tiles[y * DLVL_W + x] = T_CORRIDOR;
			x += delta(breakpoint - x);
		}
		while (y != ty)
		{
			dlvl->tiles[y * DLVL_W + x] = T_CORRIDOR;
			y += delta(ty - y);
		}
		while (x != tx)
		{
			dlvl->tiles[y * DLVL_W + x] = T_CORRIDOR;
			x += delta(tx - x);
		}
	}
	else if (dir == DIR_YXY)
	{
		breakpoint = sy + 2 + rn1(ty - sy - 4);
		while (y != breakpoint)
		{
			dlvl->tiles[y * DLVL_W + x] = T_CORRIDOR;
			y += delta(breakpoint - y);
		}
		while (x != tx)
		{
			dlvl->tiles[y * DLVL_W + x] = T_CORRIDOR;
			x += delta(tx - x);
		}
		while (y != ty)
		{
			dlvl->tiles[y * DLVL_W + x] = T_CORRIDOR;
			y += delta(ty - y);
		}
	}
}

#define FILLGRID_00	0x01
#define FILLGRID_10	0x02
#define FILLGRID_01	0x04
#define FILLGRID_11	0x08
void GenerateDungeon(dlvl_t *dlvl, uint8_t level)
{
	uint8_t roomcount;
	uint8_t placed;
	uint8_t x;
	uint8_t y;
	uint8_t w;
	uint8_t h;
	room_t rooms[ROOMGRID_W * ROOMGRID_H];
	passage_t pass[6 * ROOMGRID_W * ROOMGRID_H];
	uint8_t passcount;
	uint8_t roomptr[ROOMGRID_W * ROOMGRID_H];
	uint8_t idx;
	uint8_t idx2;
	uint8_t idx3;
	uint8_t upidx;
	uint8_t dnidx;
	uint8_t sparey;
	uint8_t sparex;
	int8_t gx;
	int8_t gy;
	uint8_t real;

	roomcount = 5 + rn1(3);
	placed = 0;
	memset(roomptr, 0xFF, ROOMGRID_W * ROOMGRID_H);

	if (level <= 1)
	{
		upidx = 0xFF;
	}
	else
	{
		upidx = rn1(roomcount);
	}
	if (level >= BRANCHDEFS[B_DUNGEONS].depth)
	{
		dnidx = 0xFF;
	}
	else
	{
		do
		{
			dnidx = rn1(roomcount);
		} while (dnidx == upidx);
	}

	while (placed < roomcount)
	{
		x = rn1(ROOMGRID_W);
		y = rn1(ROOMGRID_H);
		if (roomptr[y * ROOMGRID_W + x] != 0xFF)
		{
			continue;
		}
		rooms[placed].matrixx = x;
		rooms[placed].matrixy = y;
		rooms[placed].w = 4 + rn1(4) + rn2(4);
		rooms[placed].h = 2 + rn3(3);
		roomptr[y * ROOMGRID_W + x] = placed;
		placed++;
	}

	memset(dlvl->tiles, T_ROCK, DLVL_W * DLVL_H);
	memset(dlvl->exposed, 0, DLVL_W * DLVL_H);
	for (idx = 0; idx < placed; idx++)
	{
		sparex = (rooms[idx].w < 8) ? (8 - rooms[idx].w) : 0;
		x = 2 + rooms[idx].matrixx * 20 + rn1(4 + sparex);
		sparey = (rooms[idx].h < 6) ? (6 - rooms[idx].h) : 0;
		y = 1 + rooms[idx].matrixy * 10 + rn1(1 + sparey);
		rooms[idx].x = x;
		rooms[idx].y = y;
		if (idx == upidx)
		{
			PlaceRoom(dlvl, &rooms[idx], T_UPSTAIR, level, B_DUNGEONS);
		}
		else if (idx == dnidx)
		{
			PlaceRoom(dlvl, &rooms[idx], T_DNSTAIR, level, B_DUNGEONS);
		}
		else
		{
			PlaceRoom(dlvl, &rooms[idx], 0, level, B_DUNGEONS);
		}
	}

	passcount = 0;
	for (gy = 0; gy < ROOMGRID_H; gy++)
	{
		for (gx = 0; gx < ROOMGRID_W; gx++)
		{
			idx = gy * ROOMGRID_W + gx;
			real = (roomptr[idx] != 0xFF);
			if (real)
			{
				x = rooms[roomptr[idx]].x;
				y = rooms[roomptr[idx]].y;
				w = rooms[roomptr[idx]].w;
				h = rooms[roomptr[idx]].h;
			}
			else
			{
				// populate some bullshit room data that we may decide
				// to use for populating corridors to dead ends
				x = 2 + gx * 20;
				y = 1 + gy * 9;
				w = 7;
				h = 4;
			}
			idx2 = idx + 1;
			if (gx < ROOMGRID_W - 1 && (real || !rn1(3)) && roomptr[idx2] != 0xFF)
			{
				idx3 = roomptr[idx2];
				pass[passcount].sx = x;
				pass[passcount].sy = y;
				pass[passcount].sw = w;
				pass[passcount].sh = h;
				pass[passcount].dx = rooms[idx3].x;
				pass[passcount].dy = rooms[idx3].y;
				pass[passcount].dw = rooms[idx3].w;
				pass[passcount].dh = rooms[idx3].h;
				pass[passcount].orient = 4;
				passcount++;
			}
			idx2 = idx + 2;
			if (gx < ROOMGRID_W - 2 && (real || !rn1(3)) && roomptr[idx2 - 1] == 0xFF && roomptr[idx2] != 0xFF)
			{
				idx3 = roomptr[idx2];
				pass[passcount].sx = x;
				pass[passcount].sy = y;
				pass[passcount].sw = w;
				pass[passcount].sh = h;
				pass[passcount].dx = rooms[idx3].x;
				pass[passcount].dy = rooms[idx3].y;
				pass[passcount].dw = rooms[idx3].w;
				pass[passcount].dh = rooms[idx3].h;
				pass[passcount].orient = 4;
				passcount++;
			}
			idx2 = idx + 3;
			if (gx < ROOMGRID_W - 3 && (real || !rn1(3)) && roomptr[idx2 - 2] == 0xFF && roomptr[idx2 - 1] == 0xFF && roomptr[idx2] != 0xFF)
			{
				idx3 = roomptr[idx2];
				pass[passcount].sx = x;
				pass[passcount].sy = y;
				pass[passcount].sw = w;
				pass[passcount].sh = h;
				pass[passcount].dx = rooms[idx3].x;
				pass[passcount].dy = rooms[idx3].y;
				pass[passcount].dw = rooms[idx3].w;
				pass[passcount].dh = rooms[idx3].h;
				pass[passcount].orient = 4;
				passcount++;
			}
			idx2 = idx + ROOMGRID_W;
			if (gy < ROOMGRID_H - 1 && (real || !rn1(3)) && roomptr[idx2] != 0xFF)
			{
				idx3 = roomptr[idx2];
				pass[passcount].sx = x;
				pass[passcount].sy = y;
				pass[passcount].sw = w;
				pass[passcount].sh = h;
				pass[passcount].dx = rooms[idx3].x;
				pass[passcount].dy = rooms[idx3].y;
				pass[passcount].dw = rooms[idx3].w;
				pass[passcount].dh = rooms[idx3].h;
				pass[passcount].orient = 2;
				passcount++;
			}
#if EXTRA_CORRIDORS
			idx2 = idx + ROOMGRID_W + 1;
			if (gy < ROOMGRID_H - 1 && (real || !rn1(3)) && roomptr[idx2] != 0xFF)
			{
				idx3 = roomptr[idx2];
				pass[passcount].sx = x;
				pass[passcount].sy = y;
				pass[passcount].sw = w;
				pass[passcount].sh = h;
				pass[passcount].dx = rooms[idx3].x;
				pass[passcount].dy = rooms[idx3].y;
				pass[passcount].dw = rooms[idx3].w;
				pass[passcount].dh = rooms[idx3].h;
				pass[passcount].orient = 3;
				passcount++;
			}
			idx2 = idx - ROOMGRID_W + 1;
			if (gy == ROOMGRID_H - 1 && (real || !rn1(3)) && roomptr[idx2] != 0xFF)
			{
				idx3 = roomptr[idx2];
				pass[passcount].sx = x;
				pass[passcount].sy = y;
				pass[passcount].sw = w;
				pass[passcount].sh = h;
				pass[passcount].dx = rooms[idx3].x;
				pass[passcount].dy = rooms[idx3].y;
				pass[passcount].dw = rooms[idx3].w;
				pass[passcount].dh = rooms[idx3].h;
				pass[passcount].orient = 9;
				passcount++;
			}
#endif
		}
	}

	for (idx = 0; idx < passcount; idx++)
	{
		PlaceCorridor(dlvl, &pass[idx]);
	}

#if BOUNDED_DUNGEONS
	for (x = 0; x < DLVL_W; x++)
	{
		dlvl->tiles[x] = T_HARDROCK;
		dlvl->tiles[(DLVL_H - 1) * DLVL_W + x] = T_HARDROCK;
	}

	for (y = 0; y < DLVL_H; y++)
	{
		dlvl->tiles[y * DLVL_W] = T_HARDROCK;
		dlvl->tiles[y * DLVL_W + DLVL_W - 1] = T_HARDROCK;
	}
#endif

	dlvl->exists = 1;
}

void GenerateCatacomb(dlvl_t *dlvl, uint8_t level)
{
	AddMsg("You stumble upon an unimplemented feature! It bites! The bite was deadly.");
	GameOver();
}

uint8_t FindMonSpot(uint8_t *x, uint8_t *y)
{
	uint16_t tries;
	uint8_t tile;

	do
	{
		tries++;
		*x = rn1(DLVL_W);
		*y = rn1(DLVL_H);
		if (plyrfov(*x, *y) >= V_CANSEE)
		{
			continue;
		}
		tile = dtile(*x, *y);
		if (tile == T_FLOOR || tile == T_POOL || tile == T_IDOL)
		{
			break;
		}
	} while (tries);
	if (!tries)
	{
		*x = 0;
		*y = 0;
		return 1;
	}

	return 0;
}

uint8_t FindMonSpotNear(uint8_t x, uint8_t y, int8_t *dx, int8_t *dy)
{
	uint16_t tries;
	uint8_t tile;

	tries = 0;
	do
	{
		tries++;
		*dx = (rn1(5) - 2);
		*dy = (rn1(5) - 2);
		if (x + *dx == plyrmon.x && y + *dy == plyrmon.y)
		{
			continue;
		}
		else if (GetMonAt(x + *dx, y + *dy) != MON_NULL)
		{
			continue;
		}
		tile = dtile(x + *dx, y + *dy);
		if (tile == T_FLOOR || tile == T_POOL || tile == T_IDOL)
		{
			break;
		}
	} while (tries);
	if (!tries)
	{
		*dx = 0;
		*dy = 0;
		return 1;
	}

	return 0;
}

static const int8_t fovmatrix[4][8] = {
	{ +1, +0, +0, -1, -1, +0, +0, +1 },
	{ +0, +1, -1, +0, +0, -1, +1, +0 },
	{ +0, +1, +1, +0, +0, -1, -1, +0 },
	{ +1, +0, +0, +1, -1, +0, +0, -1 },
};

// Adapted from RogueBasin's Ruby Shadowcasting Implementation:
// http://roguebasin.roguelikedevelopment.org/index.php/Ruby_shadowcasting_implementation
static void CalcFov(uint8_t cx, uint8_t cy, uint8_t iter, float ss, float es, uint8_t radius, int8_t xx, int8_t xy, int8_t yx, int8_t yy, uint16_t id)
{
	int8_t dx;
	int8_t dy;
	uint8_t x;
	uint8_t y;
	uint8_t blocked;
	uint16_t r2;
	float ls;
	float rs;
	float nss;

	if (ss < es)
	{
		return;
	}
	r2 = radius * radius;
	for (; iter <= radius; iter++)
	{
		dx = -iter - 1;
		dy = -iter;
		blocked = 0;
		while (dx <= 0)
		{
			dx++;
			x = cx + dx * xx + dy * xy;
			y = cy + dx * yx + dy * yy;
			ls = (dx - 0.5f) / (dy + 0.5f);
			rs = (dx + 0.5f) / (dy - 0.5f);
			if (ss < rs)
			{
				continue;
			}
			else if (es > ls)
			{
				break;
			}
			else
			{
				if (dx * dx + dy * dy < r2)
				{
					dfov(x, y) = 1;
				}
				if (blocked)
				{
					if (BlocksSight(dtile(x, y)))
					{
						nss = rs;
						continue;
					}
					else
					{
						blocked = 0;
						ss = nss;
					}
				}
				else
				{
					if (BlocksSight(dtile(x, y)) && iter < radius)
					{
						blocked = 1;
						CalcFov(cx, cy, iter + 1, ss, ls, radius, xx, xy, yx, yy, id + 1);
						nss = rs;
					}
				}
			}
		}
		if (blocked)
		{
			break;
		}
	}
}

static void CalcFovAround(uint8_t x, uint8_t y, uint8_t radius)
{
	uint8_t idx;

	dfov(x, y) = 1;

	for (idx = 0; idx < 8; idx++)
	{
		CalcFov(x, y, 1, 1.0f, 0.0f, radius, fovmatrix[0][idx], fovmatrix[1][idx], fovmatrix[2][idx], fovmatrix[3][idx], 0);
	}
}

void ExposeLevel(void)
{
	uint8_t x;
	uint8_t y;

	memset(plyrdlvl.fov, 0, DLVL_W * DLVL_H);
	CalcFovAround(plyrmon.x, plyrmon.y, PLYR_FOV);
	for (y = 0; y < DLVL_H; y++)
	{
		for (x = 0; x < DLVL_W; x++)
		{
			if (dexposed(x, y) > V_WASSEEN)
			{
				dexposed(x, y) = V_WASSEEN;
			}
			if (x == plyrmon.x && y == plyrmon.y)
			{
				dexposed(x, y) = V_DETAILED;
			}
			else if (plyrfov(x, y))
			{
				dexposed(x, y) = V_CANSEE;
			}
		}
	}
}

void DrawLevel(void)
{
	uint16_t idx;

	SetColor(A_WHITE);
	for (idx = 0; idx < DLVL_W * DLVL_H; idx++)
	{
		if (plyrdlvl.exposed[idx] == V_NOTSEEN)
		{
			continue;
		}
		SetColor(TILEATTRS[plyrdlvl.tiles[idx]]);
		DrawChar(idx % DLVL_W, DLVL_BASEY + idx / DLVL_W, TILECHARS[plyrdlvl.tiles[idx]]);
	}
}

uint8_t BlocksSight(uint8_t tile)
{
	return (tile == T_ROCK || tile == T_HARDROCK);
}

uint8_t LOS_BLA(uint8_t ix, uint8_t iy, uint8_t tx, uint8_t ty)
{
	uint8_t x;
	uint8_t y;
	int8_t dx;
	int8_t dy;
	int8_t t;
	// optimized by precaching abs and sign of x/y
	uint8_t ax;
	uint8_t ay;
	int8_t sx;
	int8_t sy;

	if (tx == ix && ty == iy)
	{
		return 1;
	}

	dx = tx - ix;
	dy = ty - iy;
	ax = abs(dx) << 1;
	ay = abs(dy) << 1;
	sx = delta(dx);
	sy = delta(dy);

	x = ix;
	y = iy;

	if (ax >= ay)
	{
		t = ay - (ax >> 1);
		do
		{
			if (t >= 0)
			{
				y += sy;
				t -= ax;
			}

			x += sx;
			t += ay;

			if (x == tx && y == ty)
			{
				return 1;
			}
		} while (!BlocksSight(dtile(x, y)));
	}
	else
	{
		t = ax - (ay >> 1);
		do
		{
			if (t >= 0)
			{
				x += sx;
				t -= ay;
			}

			y += sy;
			t += ax;

			if (x == tx && y == ty)
			{
				return 1;
			}
		} while (!BlocksSight(dtile(x, y)));
	}

	return 0;
}
